import math

def int2bin(n, count):
	"""returns the binary of integer n, using count number of digits"""
	return "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])


def f(state, u):
	"""
	type: p=0,q=1,r=2
	"""
	ret = ""
	for i in range(len(u)):
		if state == 0:
			if u[i] == '0':
				ret += "1"
				state = 2
			else:
				ret += "0"
				state = 1
		else:
			ret += u[i]
			state -= 1
	return ret


def step(u, exp):
	for j in range(len(exp)):
		for i in range(exp[j]):
			u = f(j, u)
	return u

def orbit(u, exp):
	ret = []
	orig = u
	ret.append(u)
	u = step(u, exp)
	while u != orig:
		ret.append(u)
		u = step(u, exp)
	return ret

def cmp(u, exp1, exp2):
	l1 = orbit(u, exp1)
	l2 = orbit(u, exp2)

	clist = []
	for i in range(len(l1)):
		if l1[i] == l2[1]:
			clist.append((l1[i], i))
			break

	print l1
	print l2
	print clist

def cmp1(u, e1, e2):
	max = 100
	for i in range(max):
		w1 = step(u, e1)
		w2 = step(u, (e2[0], e2[1] + i, e2[2]))
		print w1, w2
		if w1 == w2 and i != 0:
			print "len: " + str(len(u)) + ", count: " + str(i)
			break

def tester():
	cap = 5
	for a in range(cap):
		for b in range(cap):
			for c in range(cap):
				for d in range(cap):
					for e in range(cap):
						for f in range(cap):
							e1 = (a,b,0)
							e2 = (d,e,0)
							l = [a,b,c,d,e,f]
							length = max(l) + 1
							w = ["0"] * length
							s = "".join(w)
							if step(s, e1) == step(s, e2) and e1 != e2:
								print "counterexample: ", str(e1), \
								str(e2), str(s)


def tester2(e1):
	cap = 20
	
	for l in range(10):
		length = l + 3
		word = "".join(["0"] * length)

		a1 = 2 ** math.ceil(length / 2)
		a2 = 2 ** math.floor(length / 2)
		print "testing wordlen: ", length, int(a1), int(a2)
	
		# create the accept list
		accept = []

		
		for a in range(cap):
			for b in range(cap):
				e2 = (a,b,e1[2])

				o1 = orbit(word, e1)
				o2 = orbit(word, e2)
				if o1 == o2:
					print "equal: ", e1, e2, word

def orbitcheck(w1, w2, func):
	l1 = orbit(w1, func)
	l2 = orbit(w2, func)
	if sorted(l1) == sorted(l2):
		return True
	return False

def orbittest(length, func):
	for k in range(2 ** length):
		for t in range(1, length-2):
			w = int2bin(k, length)
			l = orbit(w, func)

			newl = []
			for x in l:
				if x[:t] == w[:t]:
					newl.append(x[t:])
			
			# check that no two elements of newl are in the same orbit
			for i in range(len(newl)):
				for j in range(len(newl)):
					if orbitcheck(newl[i], newl[j], func) and i != j:
						print newl[i], newl[j], l, t
						return False
	return True

def checkorbits(length, e1, e2):
	for k in range(2 ** length):
		w = int2bin(k, length)
		l1 = orbit(w, e1)
		l2 = orbit(w, e2)

		for i in l1:
			for j in l2:
				if i == j and i != w:
					print i
					return False
	return True

def checkcounterex(e1, e2):
	

print checkorbits(1, (1,0,0), (0,1,0))

# print orbittest(5, (1,0,0))

# tester2((1, 3, 0))

# tester()

# cmp("000", (3, 1, 0), (1, 1, 0))

# print orbit("0000", (1, 1, 0))

# cmp("000", (1,1,0), (5,1,0))
